#include <iostream>
#include <vector>
#include <functional>
using namespace std;
/*
整数可以被看作是其因子的乘积。

例如：

8 = 2 x 2 x 2;
  = 2 x 4.
请实现一个函数，该函数接收一个整数 n 并返回该整数所有的因子组合。

注意：

你可以假定 n 为永远为正数。
因子必须大于 1 并且小于 n。
示例 1：

输入: 1
输出: []
示例 2：

输入: 37
输出: []
示例 3：

输入: 12
输出:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]
示例 4:

输入: 32
输出:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/factor-combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

class Solution
{
public:
    vector<vector<int>> getFactors(int n)
    {
        if (n == 1)
            return {};
        vector<int> factors;
        for (int i = 2; i < n; i++)
        {
            if (!(n % i))
                factors.emplace_back(i);
        }
        vector<vector<int>> res;
        vector<int> candidates;
        function<void(int, long)> backtracking = [&](int p, long num) -> void
        {
            if (num == n)
                return res.push_back(candidates);
            for (int i = p; i < factors.size(); i++)
            {
                if (num * factors[i] > n)
                    return;
                candidates.emplace_back(factors[i]);
                backtracking(i, num * factors[i]);
                candidates.pop_back();
            }
        };
        backtracking(0, 1);
        return res;
    }

    //Another Version 'DFS'
private:
    vector<vector<int>> res;
    void dfs(vector<int> &&m)
    {
        res.emplace_back(m);
        for (int i = *++rbegin(m); i * i <= m.back(); i++)
        {
            if (m.back() % i == 0)
            {
                vector<int> temp(m.begin(), m.end() - 1);
                temp.push_back(i);
                temp.push_back(m.back() / i);
                dfs(move(temp));
            }
        }
    }

public:
    vector<vector<int>> getFactors(int n)
    {
        for (int i = 2; i * i <= n; i++)
        {
            if (n % i == 0)
                dfs({i, n / i});
        }
        return res;
    }
};